package dynamic.dpPack;

/**
 * 分组背包
 * 每一类只能选择一个商品
 */
public class GroupPack {

    private int packGroup(int V, int[] c, int[] w, int[] s) {
        int[] dp = new int[V+1];
        int pos = 0;  // 标记位置
        for (int i=1; i<=s.length; i++) {  // 物品种类
            for (int j=V; j>=c[i-1]; j--) {
                for (int k=0; k<s[i-1]; k++) {  // 插入每组数据的max
                    dp[j] = Math.max(dp[j], dp[j-c[k+pos]]+w[k+pos]);
                    pos++;
                }
            }
        }
        return dp[V];
    }

    public static void main(String[] args) {
        int[] c = new int[]{2, 4, 4, 5};  // 体积
        int[] w = new int[]{1, 2, 3, 4};  // 价格
        int[] s = new int[]{2, 1, 1};  // 每组个数
        int V = 5;
        GroupPack groupPack = new GroupPack();
        int ans = groupPack.packGroup(V, c, w, s);
        System.out.println("dp ans:"+ans);
    }

}
